package subject.huisu;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class permute {
    public List<List<Integer>> permute1(int[] nums) {
        // 准备结果列表
        List<List<Integer>> res = new ArrayList<>();

        // 将输入数组转为列表（方便操作）
        List<Integer> output = new ArrayList<>();
        for (int num : nums) output.add(num);

        // 开始回溯搜索
        backtrack(nums.length, output, res, 0);
        return res;
    }

    void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
        // 终止条件：所有位置都已填满
        if (first == n) {
            res.add(new ArrayList<>(output)); // 保存当前排列
            return;
        }

        // 从first位置开始尝试所有可能
        for (int i = first; i < n; i++) {
            // 1. 交换：把第i个元素放到first位置
            Collections.swap(output, first, i);

            // 2. 递归：处理下一个位置(first+1)
            backtrack(n, output, res, first + 1);

            // 3. 回溯：恢复交换前的状态
            Collections.swap(output, first, i);
        }
    }
}
